package com.taldh.algorithm.二分查找法;

import org.junit.Assert;
import org.junit.Test;

import java.util.Arrays;
import java.util.stream.Collectors;

public class NextGreatestLetter {

    public char nextGreatestLetter(char[] letters, char target) {
//        int len = letters.length;
//        if (letters[0] > target || letters[len - 1] <= target) {
//            return letters[0];
//        }
//        for (char letter : letters) {
//            if (letter > target) {
//                return letter;
//            }
//        }
//        return 'a';
        //二分查找法

        int lo = 0, hi = letters.length;
        while (lo < hi) {
            int mi = lo + (hi - lo) / 2;
            if (letters[mi] <= target) lo = mi + 1;
            else hi = mi;
        }
        return letters[lo % letters.length];
    }

    @Test
    public void test() {
        Assert.assertEquals('c',nextGreatestLetter(new char[]{'c', 'f', 'j'}, 'a'));
    }
}